import numpy as np
import time


# 比较和交换函数
def compare_and_swap(a, i, j, dir):
    if dir == (a[i] > a[j]):

        # 交换元素
        a[i], a[j] = a[j], a[i]

# 双调排序的递归函数
def bitonic_merge(a, low, count, dir):
    if count > 1:
        k = count // 2
        for i in range(low, low + k):
            compare_and_swap(a, i, i + k, dir)
        bitonic_merge(a, low, k, dir)
        bitonic_merge(a, low + k, k, dir)

# 初始化双调序列并排序
def bitonic_sort(a, low, count, dir):
    if count > 1:
        k = count // 2
        #print(count, low, k, low+k, k, dir)
        #print(a)
        #print()
        bitonic_sort(a, low, k, 1)
        bitonic_sort(a, low + k, k, 0)
        bitonic_merge(a, low, count, dir)

# 主函数
def main():
    arr = np.random.randint(0, 1000000, 1000000)
    #print("Original array:", arr)
    n = len(arr)
    
    # 记录开始时间
    start_time = time.time()

    # 调用函数    # 初始化为升序
    bitonic_sort(arr, 0, n, 1)

    # 记录结束时间
    end_time = time.time()

    # 计算并打印运行时间
    print(f"函数运行时间为：{end_time - start_time} 秒")

   # print("Sorted array:", arr)

if __name__ == "__main__":
    main()
